Various algorithms have been proposed to compress 3D meshes efficiently since the early 1990s. Early work however mostly concentrates on compressing single connected 3D models with smooth surface and small triangles. In most of today's large 3D engineering models there are a large number of small to medium sized connected components, each having up to a few hundred polygons on average. Often this type of models has a number of geometric features or components that are repeated in various positions, scales and orientations. Such models are called multi-connected. The components are compressed separately, causing a relatively inefficient compression. The compression performance can be greatly increased by removing the redundancy between different connected components. Various methods for automatically discovering repeating geometric features in large 3D engineering models are known. Their respective positions are defined by the 3D position of at least one reference point per component. However, one problem is how to encode the position of the respective reference points.
Most of the efficient compression algorithm for spatial points are spatial tree based, e.g. kd-tree based (as in [OG02]: “Geometric compression for interactive transmission” by O. Devillers, P. Gandoin, IEEE Visualization, 2000, pp. 319-326) or octree based (as in [PK05]: “Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition” by J. L. Peng, C.-C. Jay Kuo, ACM SIGGRAPH/ACM Transactions on Graphics 24(3), 609-616, 2005).
These algorithms divide a given space into segments, and provide the number of input spatial points lying in each particular segment. Thus, they organize the input spatial points by an implicit spatial tree. Then they traverse the tree structure and record the necessary information for later restoring the input points. When building the spatial tree, a cell is recursively subdivided, until each non-empty cell is small enough to contain only one vertex and enable a sufficiently precise reconstruction of the point position.
Cells correspond to nodes. Initially, the entire bounding box of all 3D points is regarded as a cell or node. As the point positions can be restored from the bounding box of the corresponding cells, the spatial tree based algorithms can achieve multi-resolution compression at the same compression ratio as single-resolution compression algorithms.
An example of the method used in [OG02] is shown in FIG. 1. Each time when a parent cell is subdivided into two child cells, the number of points in one (e.g. left or upper) of the two child cells is encoded. If the parent cell contains p points, the number of points in one of the child cells can be encoded using log2 (p+1) bits with an arithmetic coder.
Different from that, [PK05] subdivides a non-empty cell into eight cells, and encodes only the indices of non-empty child-cells after each cell subdivision. In order to improve coding efficiency, [PK05] estimates the pseudo-probability of various T-tuples to be the group of non-empty child cells. The traversal orders of child cells are according to a probability descending order.
However, for enabling compact storage and fast transmission, it is a continuous problem how to increase the efficiency of compression algorithms.